proCounter = 0

binOps = { 'xor' : '^',
           'add' : '+',
           'sub' : '-',
           'sar' : '>>',
           'shl' : '<<'}
def interpret( ast, instrCount ):
                 
    
    def zeroInstr( x ):
        retList = []
        if x[0] == 'ret':
            destExpr = reformatExpr(('reg', 'esp'),1)
            inpExpr = reformatExpr(('mod_stack', 4),0)
            retList += [(destExpr,inpExpr)]
        elif x[0] == 'cdq':
            destExpr = reformatExpr(('reg', 'edx'),1)
            inpExpr = reformatExpr(('sign_extend', 'eax'),0)
            retList += [(destExpr,inpExpr)]
        else:
            return []
        return retList

    def singleInstr( x ):
        retList = []
        if x[0] == 'call':
            destExpr = reformatExpr(('reg', 'esp'), 1)
            inpExpr = reformatExpr(('mod_stack', -4), 0)
            retList += [(destExpr,inpExpr)]
        elif x[0] == 'push':
            destExpr = reformatExpr(('reg', 'esp'),1)
            inpExpr = reformatExpr(('mod_stack', -4),0)
            retList += [(destExpr,inpExpr)]
            destExpr = reformatExpr(('place_stack',),1)
            inpExpr = reformatExpr(x[1],0)
            retList += [(destExpr,inpExpr)]
        elif x[0] == 'pop':
            destExpr = reformatExpr(x[1],1)
            inpExpr = reformatExpr(('pull_stack',),0)
            retList += [(destExpr,inpExpr)]
            destExpr = reformatExpr(('reg', 'esp'),1)
            inpExpr = reformatExpr(('mod_stack', 4),0)
            retList += [(destExpr,inpExpr)]
        else:
            return []
            
        #refDest = reformatExprs( destExpr, 1 )
        #refInp = reformatExprs( inpExpr, 0 )
        return retList

    def doubleInstr( x ):
        retList = []
        if x[0] in ('mov','movdword','movword','movbyte'):
            destExpr = reformatExpr(x[1],1)
            inpExpr = reformatExpr(x[2],0)
            retList += [(destExpr,inpExpr)]
        elif x[0] in binOps:
            destExpr = reformatExpr(x[1],1)
            inpExpr = reformatExpr((binOps[x[0]], x[1], x[2]),0)
            retList += [(destExpr,inpExpr)]
        elif x[0] == 'cmp':
            destExpr = reformatExpr(('reg', 'zf'),1)
            inpExpr = reformatExpr(('==', x[1], x[2]),0)
            retList += [(destExpr,inpExpr)]
        else:
            return []

        return retList
                         

    def tripleInstr( x ):
        retList = []
        if x[0] == 'imul':
            destExpr = reformatExpr(x[1],1)
            inpExpr = reformatExpr(x[2],0)
            retList += [(destExpr,inpExpr)]
        else:
            return []
            
        return retList

    def setName( name, val ):
        return "put(%d,%s,%s)." % ( instrCount, str(reformat(name)), str(reformat(val)) )

    def modifyName( name, modification ):
        return "put(%(instr)d,%(name)s,%(name)s+V) :- get(%(pInstr)d,%(name)s,%(name)s+X), V is X + %(mod)s." % \
               { 'instr':instrCount,'pInstr': instrCount-1,'name':reformat(name),'mod':str(reformat(modification)) }

    def reformatExprs( ss, isDest = 0 ):
        left = []
        right = []
        for s in ss:
            (subL,subR) = reformatExpr( s, isDest )
            left += [subL]
            right += [subR]
        return (left, right)

    def reformatExpr( s, isDest = 0 ):
        left = ""
        right = []
        global proCounter
        proCounter += 1
        if s[0] == 'imm':
            left += str(s[1])
        elif s[0] == 'reg':
            if isDest:
                left += str(s[1])
            else:
                left += str('X'+str(proCounter))
                right += ['get(' + str(instrCount - 1) + ',' + s[1] + ',X' + str(proCounter) + ')']
        elif s[0] == 'deref':
            recursRes = reformatExpr( s[1] )
            right.extend( recursRes[1] )
            if isDest == 0: # if input, go one step further and lookup in prolog
                left = 'X' + str(proCounter)
                right.extend( ['get(' + str(instrCount-1) + ',deref(' + recursRes[0] + '),X' + str(proCounter) + ')' ] )
            else:
                left = 'deref(' + recursRes[0] + ')'
        elif s[0] in ['+','-','*','^','>>','==','<<']:
            # ideally we would like prolog to do this work, but swi prolog doesnt at the moment
            # possibly later implement something with prolog, such as catches (could get slow though)
            if s[1][0] == 'reg' and s[1][1] == 'esp' and s[2][0] == 'imm':
                left = 'W'
                right = ['get(' + str(instrCount-1) + ',esp,M)', 'W is M + ' + str(s[2][1]) ]
            else:    
                rec1 = reformatExpr( s[1] )
                rec2 = reformatExpr( s[2] )
                #left += rec1[0] + s[0] + rec2[0]
                if s[0] == '+' and rec2[0][0] == '-':
                    left += rec1[0] + '-' + rec2[0][1:]
                else:
                    left += rec1[0] + s[0] + rec2[0]
                right.extend( rec1[1] )
                right.extend( rec2[1] )
        elif s[0] == 'sign_extend':
            left += "sign_extend(X)"
            right += ['get(' + str(instrCount - 1) + ',eax,X)']
        elif s[0] == 'mod_stack': # special case ('mod_stack', integer)
            left += "X"
            right += ['get(' + str(instrCount - 1) + ',esp,Z)', 'X is Z + ' + str(s[1])]
        elif s[0] == 'place_stack': # puts the dereferenced top of stack into left
            left = 'deref(U)'
            right = ['get(' + str(instrCount) + ',esp,U)']
        elif s[0] == 'pull_stack': # puts top of stack into left
            left = 'V'
            right = ['get(' + str(instrCount-1) + ',esp,U)', 'get(%d,deref(%s),%s)' % (instrCount-1,'U','V')]
        else:
            raise Exception()
        return (left, right)
    

    def makeLookup( name, binding ):
        return "get(%d,%s,%s)" % (instrCount - 1,name,binding)

    
    def reformat( x ):
        if type(x) is type(0):
            return x
        elif type(x) is type(""):
            return x
        elif x[0] == 'imm':
            return x[1]
        elif x[0] == 'reg':
            return x[1]
        elif x[0] == 'deref':
            return lookup( x )
        else:
            #print "reformat exc!"
            raise Exception()

    def evalExp( x ):
        if x[0] == '+':
            return evalExp(x[1]) + evalExp(x[2])
        elif x[0] == '-':
            return evalExp(x[1]) - evalExp(x[2])
        elif x[0] == '*':
            return evalExp(x[1]) * evalExp(x[2])
        else:
            return lookup(x)
        
    def lookup( x ):
        if type(x) is type(0):
            return x
        elif type(x) is type(""):
            return x
        elif x[0] == 'imm':
            return x[1]
        elif x[0] == 'reg': 
            return getattr( context, x[1][0].upper() + x[1][1:] )
        elif x[0] == 'deref':
            #print evalExp(x[1]
            #return process.readInt( evalExp(x[1]), 4 )
            return 'oops not implemented'
        else:
            #print "lookup exc!"
            raise Exception()
        
    def traverseForDerefs( x ):
        for i in xrange(1,len(x)):
            if ( x[i][0] == 'deref' ):
                pass
    #print str(instrCount)
    #print "doing stuff"
    instructionNum = instrCount
    instrFuns = [ zeroInstr, singleInstr, doubleInstr, tripleInstr ]
    #print "performing action"
    actions = instrFuns[ len(ast) - 1 ]( ast )
    if (len(actions) == 0):
        print "Possibly unrecognized instruction:" + str(ast)
        return ""
    #print "returning"
    #(refDests, refInps) = actions
    retVal = ""
    for (refDest, refInp) in actions:
        #print refDest
        #print refInp
        if (len(refDest[1]) + len(refInp[1])) == 0: # nothing on RHS
            retVal += '\nput(' + str( instrCount ) + ',' + refDest[0] + ',' + refInp[0] + ').'
        else:
            retVal += '\nput(' + str( instrCount ) + ',' + refDest[0] + ',' + refInp[0] + ') :- ' + (',').join(refDest[1] + refInp[1]) + '.'
    return retVal
        

#print(interpret( ('mov',('reg', 'eax'),('imm', 50)), 1) )

